package com.lg.partition12;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/23 9:13
 */
public class P1119灾后重建_floyd {

    private static final int N = 210, INF = 0x3f3f3f3f;
    private static int[] hw = new int[N];
    private static int[][] f = new int[N][N];
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        ss = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) hw[i] = Integer.parseInt(ss[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j] = i == j ? 0 : INF;
            }
        }
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), c = Integer.parseInt(ss[2]);
            f[a][b] = f[b][a] = c;
        }
        int q = Integer.parseInt(reader.readLine()), k = 0;
        //按照时间顺序处理询问
        while (q-- > 0) {
            ss = reader.readLine().split(" ");
            int a = Integer.parseInt(ss[0]), b = Integer.parseInt(ss[1]), t = Integer.parseInt(ss[2]);
            while (hw[k] <= t && k < n) {
                //按照时间顺序更新节点
                floyd(k);
                k++;
            }
            if (hw[a] > t || hw[b] > t || f[a][b] == INF) writer.write("-1\n");
            else writer.write(f[a][b] + "\n");
        }
        writer.flush();
    }

    private static void floyd(int k) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i][j] > f[i][k] + f[k][j]) {
                    f[i][j] = f[j][i] = f[i][k] + f[k][j];
                }
            }
        }
    }
}
